package com.leetcode.test.hash;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/explore/learn/card/hash-table/205/practical-application-hash-map/811/
 * <p>
 * 解题：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
 */
public class 两数之和 {

	@Test
	public void test() {
		int[] array = twoSum(new int[]{3, 3}, 6);

		// 应该是[0,1]
		System.out.println(Arrays.toString(array));
	}

	// 数组可能重复
	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();

		// 把所有元素、下标添加到map中
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], i); // 当指重复，valu是数组最后的元素
		}

		for (int i = 0; i < nums.length; i++) {
			int diff = target - nums[i];

			// 数组存在这个元素 && 不是当前元素
			if (map.containsKey(diff) && map.get(diff) != i) {
				return new int[]{i, map.get(diff)};
			}
		}

		return new int[0];
	}
}
